package com.zs.letcode.trie;

/**
 * 添加与搜索单词 - 数据结构设计
 * 请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
 * <p>
 * 实现词典类 WordDictionary ：
 * <p>
 * WordDictionary() 初始化词典对象
 * void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
 * bool search(word) 如果数据结构中存在字符串与word 匹配，则返回 true ；否则，返回 false 。word 中可能包含一些 '.' ，每个. 都可以表示任何一个字母。
 *
 * <p>
 * 示例：
 * <p>
 * 输入：
 * ["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
 * [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
 * 输出：
 * [null,null,null,null,false,true,true,true]
 * <p>
 * 解释：
 * WordDictionary wordDictionary = new WordDictionary();
 * wordDictionary.addWord("bad");
 * wordDictionary.addWord("dad");
 * wordDictionary.addWord("mad");
 * wordDictionary.search("pad"); // return False
 * wordDictionary.search("bad"); // return True
 * wordDictionary.search(".ad"); // return True
 * wordDictionary.search("b.."); // return True
 *
 * <p>
 * 提示：
 * <p>
 * 1 <= word.length <= 500
 * addWord 中的 word 由小写英文字母组成
 * search 中的 word 由 '.' 或小写英文字母组成
 * 最多调用 50000 次 addWord 和 search
 * 相关标签
 * 深度优先搜索
 * 设计
 * 字典树
 * 字符串
 * <p>
 * Java
 * <p>
 * <p>
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/trie/x0jtri/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/8/6 10:05
 */
public class Chapter4 {

    public static void main(String[] args) {

    }

    private static class WordDictionary {

        /**
         * Initialize your data structure here.
         */
        Trie root;

        public WordDictionary() {
            root = new Trie();
        }

        public void addWord(String word) {
            //防止破坏头部节点，新定义一个head
            Trie head = root;
            for (char c : word.toCharArray()) {
                int index = c - 'a';
                //当子节点不存在该字符时，新生成一个子节点
                if (head.next[index] == null) {
                    head.next[index] = new Trie();
                }
                //指向子节点
                head = head.next[index];
            }
            //最后的head对应的就是该单词最后的字符，此时结束符为true，表示存在一个以该字符结尾的单词
            head.isEnd = true;
        }

        public boolean search(String word) {
            Trie head = root;
            return dfs(word, 0, head);
        }

        private boolean dfs(String word, int index, Trie head) {
            //当遍历到所查询单词末尾时，刚好该字符为结束符，即查询命中，返回true，否则返回false
            if (index == word.length()) {
                if (head.isEnd) return true;
                return false;
            }
            char c = word.charAt(index);
            //遇到‘.’进行26个子节点的遍历，子节点不为null则进行递归，命中一次直接返回true
            if (c == '.') {
                for (int i = 0; i < 26; i++) {
                    if (head.next[i] != null) {
                        if (dfs(word, index + 1, head.next[i])) return true;
                    }
                }
            } else {
                //定向寻找，当对应子节点为null时直接返回false，否则进行递归
                int t = c - 'a';
                if (head.next[t] != null) {
                    if (dfs(word, index + 1, head.next[t])) return true;
                }
            }
            return false;
        }

        private class Trie {
            //子节点集合，对应26个英文字母，大小为26
            Trie[] next;
            //单词结束符，用来判断截至到该节点的单词是否存在
            boolean isEnd = false;

            Trie() {
                next = new Trie[26];
            }
        }
    }

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */
}
